package com.leetcode.algorithm.y22.m09.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 437. 路径总和 III
 * 
 * https://leetcode.cn/problems/path-sum-iii/
 * 
 * @author jie.deng
 *
 */
class Question0437Solution01 {

	public int pathSum(TreeNode root, int targetSum) {
		if (root == null) {
			return 0;
		}
		// 先序递归遍历每个节点，再以每个节点作为起始点递归寻找满足条件的路径。
		int sum = dfs(root, targetSum);
		sum += pathSum(root.left, targetSum);
		sum += pathSum(root.right, targetSum);
		return sum;
	}

	// DFS
	// 先序遍历
	private int dfs(TreeNode root, long targetSum) {
		int pathCnt = 0;
		if (root == null) {
			return pathCnt;
		}
		targetSum -= root.val;
		if (targetSum == 0) {
			pathCnt++;
		}
		pathCnt += dfs(root.left, targetSum);
		pathCnt += dfs(root.right, targetSum);
		return pathCnt;
	}

}